package own.stu.jobgib.playown.alg.leetcode.editor.cn;

//给你链表的头节点 head 和一个整数 k 。 
//
// 交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [1,2,3,4,5], k = 2
//输出：[1,4,3,2,5]
// 
//
// 示例 2： 
//
// 
//输入：head = [7,9,6,6,7,8,3,0,9,5], k = 5
//输出：[7,9,6,6,8,7,3,0,9,5]
// 
//
// 示例 3： 
//
// 
//输入：head = [1], k = 1
//输出：[1]
// 
//
// 示例 4： 
//
// 
//输入：head = [1,2], k = 1
//输出：[2,1]
// 
//
// 示例 5： 
//
// 
//输入：head = [1,2,3], k = 2
//输出：[1,2,3]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点的数目是 n 
// 1 <= k <= n <= 105 
// 0 <= Node.val <= 100 
// 
// Related Topics 链表 
// 👍 14 👎 0



public class SwappingNodesInALinkedList{
    public static void main(String[] args) {
        Solution solution = new SwappingNodesInALinkedList().new Solution();
        ListNode head = new ListNode(1);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(3);
        ListNode head4 = new ListNode(4);
        ListNode head5 = new ListNode(5);

        head.next = head2;
        head2.next = head3;
        head3.next = head4;
        head4.next = head5;

        solution.swapNodes(head, 2);
        
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapNodes(ListNode head, int k) {

        if (head == null) {
            return head;
        }

        int len = length(head);
        ListNode dummy = new ListNode();
        dummy.next = head;

        ListNode first = null;
        ListNode sec = null;
        int i = 0;

        ListNode cur = dummy;
        while (cur != null) {
            cur = cur.next;
            i += 1;
            if (i == k) {
                first = cur;
            }
            if (i == len - k + 1) {
                sec = cur;
            }
        }

        if(first == sec){
            return head;
        }

        int tmpVal = first.val;
        first.val = sec.val;
        sec.val = tmpVal;

        return dummy.next;
    }

    private int length(ListNode node) {
        int len = 0;

        while(node != null){
            node = node.next;
            len += 1;
        }

        return len;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
